package cn.hughie.str;

import java.util.Arrays;

/**
 * @Author yuh
 * @Date Created in 上午7:30 2018/5/19
 * @Description 等长低位字符串排序
 * 排序复杂度是 利用字符串的长度*Math.max(字符串数组长度,字母表的长度) 就中文来说 一般是后者
 */
public class EqualLenthStrSort {

    public static void eqLenStrSort(String[] strs, int w) {
        String[] aux = new String[strs.length];
        int[] count = new int[Short.MAX_VALUE + 1];
        int n = strs.length;
        for (int i = w - 1; i >= 0; i--) {
            //从最后一位开始统计频率
            Arrays.fill(count,0);
            for (int j = 0; j < n; j++) {
                //这个位置 之所以加一就是因为把前一组的次数给到后一组 当后一组开始遍历的时候 拿到的直接就是起始的索引
                count[strs[j].charAt(i) + 1]++;
            }
            //后一组保存前一组次数 得到初始索引位置
            for (int j = 0; j < count.length - 1; j++) {
                count[j + 1] += count[j];
            }
            //分类
            for (int j = 0; j < strs.length; j++) {
                aux[count[strs[j].charAt(i)]++] = strs[j];
            }
            //回写
            System.arraycopy(aux, 0, strs, 0, aux.length);
        }
    }

    public static void main(String[] args) {
        String[] strs = {"♥️1", "♥️1", "♥️1", "♦️2"};
        long l = System.currentTimeMillis();
        eqLenStrSort(strs, 3);
        //Arrays.sort(strs);
        System.out.println(System.currentTimeMillis()-l);
        System.out.println(Arrays.toString(strs));
    }
}
